
//1019.链表中的下一个更大节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        //因为是链表,所以从前往后遍历更方便,记录还没有找到答案的数据
        stack<pair<int,int>> st;
        
        int n=0,i=0;
        ListNode* cur=head;
        while(cur)    //统计链表的长度
        {
            cur=cur->next;
            n++;
        }
        vector<int> ret(n,0);
        cur=head;
        while(cur)
        {
            while(!st.empty()&&st.top().first<cur->val)   //将栈中前面的数据进行更新
            {
                int index=st.top().second;
                ret[index]=cur->val;
                st.pop();
            } 
            st.push({cur->val,i});
            i++;
            cur=cur->next;
        }
        return ret;
    }
};